// 分治 - 归并
// 归并的核心思路就是先将数组分左右两块
// 再把左边数组排序，右边数组排序
// 再合并两个有序数组
// 类似于二叉树的后续遍历
// 典型的应用场景就是找逆序对 - 逆序对涉及到选择一左一右两个元素,这就是在合并两个有序数组涉及的操作,合并时统计逆序对数即可
// 找每个元素的逆序对的数量 - 关键的操作就是就是绑定 数组元素和下标 ,绑定方式就是新建一个同等规模的数组,同样进行归并排序的流程

// 例题 3：
// 给你一个整数数组 nums ，按要求返回一个新数组 counts 。
// 数组 counts 有该性质： counts[i] 的值是  nums[i] 右侧小于 nums[i] 的元素的数量。
//
//        示例 1：
//
//        输入：nums = [5,2,6,1]
//        输出：[2,1,1,0]
//        解释：
//        5 的右侧有 2 个更小的元素 (2 和 1)
//        2 的右侧仅有 1 个更小的元素 (1)
//        6 的右侧有 1 个更小的元素 (1)
//        1 的右侧有 0 个更小的元素
//        示例 2：
//
//        输入：nums = [-1]
//        输出：[0]
//        示例 3：
//
//        输入：nums = [-1,-1]
//        输出：[0,0]
//
//
//        提示：
//
//        1 <= nums.length <= 105
//        -104 <= nums[i] <= 104

// 解题思路:
// 数组/下标数组分左右两块 - 递归排序
// 合并两个有序数组/下标数组  - 通过 原数组元素和下标的对应关系,维护原数组元素对应的逆序对数量
// 还原 数组 和 下标数组

import java.util.*;

public class CountSmaller {
    int[] res;
    int[] index;
    int[] tmp;
    int[] tmpIndex;
    public List<Integer> countSmaller(int[] nums) {
        int n = nums.length;
        res = new int[n];
        index = new int[n];
        tmp = new int[n];
        tmpIndex = new int[n];
        for(int i = 0; i < n; i++) index[i] = i;
        mergeSort(nums, 0, n - 1);
        List<Integer> ret = new ArrayList<>();
        for(int i = 0; i < n; i++) ret.add(res[i]);
        return ret;
    }
    public void mergeSort(int[] nums, int left, int right){
        if(left >= right) return;
        int mid = left + (right - left) / 2;
        mergeSort(nums, left, mid);
        mergeSort(nums, mid + 1, right);
        int cur1 = left; int cur2 = mid + 1;
        int cur = 0;
        while(cur1 <= mid && cur2 <= right){
            if(nums[cur1] <= nums[cur2]) {
                tmp[cur] = nums[cur2];
                tmpIndex[cur++] = index[cur2++];
            }else{
                res[index[cur1]] += (right - cur2 + 1);
                tmp[cur] = nums[cur1];
                tmpIndex[cur++] = index[cur1++];
            }
        }
        while(cur1 <= mid) {
            tmp[cur] = nums[cur1];
            tmpIndex[cur++] = index[cur1++];
        }
        while(cur2 <= right) {
            tmp[cur] = nums[cur2];
            tmpIndex[cur++] = index[cur2++];
        }
        for(int i = left; i <= right; i++) {
            nums[i] = tmp[i - left];
            index[i] = tmpIndex[i - left];
        }
    }
}
